package myself.a005Heap;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/24
 * Time 13:25
 * Mail 739153436@qq.com
 */
public class ConverMax {

    // 笨办法，枚举计数实现，时间复杂度是 O((max-min)*N)
    public static int maxCover1(int[][] lines) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int[] ints : lines) {
            min = Math.min(min, ints[0]);
            max = Math.max(max, ints[1]);
        }
        double point = min + 0.5;
        int result = 0;
        while (point < max) {
            int count = 0;
            for (int[] line : lines) {
                if (line[0] < point && line[1] > point) {
                    count++;
                }
            }
            result = Math.max(count, result);
            point += 0.5;
        }
        return result;
    }

    // 使用堆实现，时间复杂度是 O(N*logN)
    public static int maxCover2(int[][] lines) {
        // 排序
        Line[] lns = new Line[lines.length];
        for (int i = 0; i < lines.length; i++) {
            lns[i] = new Line(lines[i][0], lines[i][1]);
        }
        Arrays.sort(lns, (o1, o2) -> o1.start - o2.start);
        // 遍历放堆，进行计数
        int result = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < lns.length; i++) {
            heap.add(lns[i].end);
            // 小根堆做多总共出 N 个数，总共最多进 N 个数，所以小根堆的时间复杂度就是 logN
            while (!heap.isEmpty() && heap.peek() <= lns[i].start) {
                heap.poll();
            }
            result = Math.max(result, heap.size());
        }
        // 返回最大值
        return result;
    }

    public static class Line {
        public int start;
        public int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}
